﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
using namespace std;

////////一、递归-回溯-剪枝综合练习
////1.全排列
class Solution {
    vector<vector<int>> vv;
    vector<int> path;
    int vis[15] = { 0 };
public:
    vector<vector<int>> permute(vector<int>& nums)
    {
        dfs(nums);
        return vv;
    }
    void dfs(vector<int>& nums)
    {
        if (path.size() == nums.size())
        {
            vv.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            if (!vis[i])
            {
                path.push_back(nums[i]);
                vis[i] = 1;
                dfs(nums);//符合要求才调用dfs
                vis[i] = 0;
                path.pop_back();
            }
        }
    }
};


////2.子集
 class Solution {
     vector<vector<int>> vv;
     vector<int> path;
 public:
     vector<vector<int>> subsets(vector<int>& nums) 
     {
         dfs(nums,0);
         return vv;
     }
     void dfs(vector<int>& nums,int pos)
     {
         if(pos==nums.size())//当[1,2,3]选择的位置n==nums.size()就代表一条路径选择完
         {
             vv.push_back(path);
             return ;
         }
         path.push_back(nums[pos]);
         dfs(nums,pos+1);//选择第pos个元素,递归到下一层;
         path.pop_back();

         dfs(nums,pos+1);//不选择直接递归到下一层;
     }
 };


class Solution {
    vector<vector<int>> vv;
    vector<int> path;
public:
    vector<vector<int>> subsets(vector<int>& nums)
    {
        dfs(nums, 0);
        return vv;
    }
    void dfs(vector<int>& nums, int pos)
    {
        vv.push_back(path);
        for (int i = pos; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }
};



////3.找出所有的子集异或总和再求和
 class Solution {
     int sum=0;
     int ret=0;
 public:
     int subsetXORSum(vector<int>& nums) 
     {
         dfs(nums,0);
         return ret;
     }
     void dfs(vector<int>&nums,int pos)
     {
         if(pos==nums.size())
         {
             ret+=sum;
             return;
         }
         //选当前的数字；
         sum^=nums[pos];
         dfs(nums,pos+1);
         sum^=nums[pos];
         //不选当前的数字：
         dfs(nums,pos+1);
     }
 };



class Solution {
    int sum = 0;
    int ret = 0;
public:
    int subsetXORSum(vector<int>& nums)
    {
        dfs(nums, 0);
        return ret;
    }
    void dfs(vector<int>& nums, int pos)
    {
        ret += sum;
        for (int i = pos; i < nums.size(); i++)
        {
            sum ^= nums[i];
            dfs(nums, i + 1);
            sum ^= nums[i];
        }
    }
};


////4.全排列 2
class Solution {
    vector<int> path;
    vector<vector<int>> vv;
    int vis[10] = { 0 };
public:
    vector<vector<int>> permuteUnique(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return vv;
    }
    void dfs(vector<int>& nums, int pos)
    {
        if (pos == nums.size())
        {
            vv.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            //if(!vis[i]&&(i==0||nums[i]!=nums[i-1]||vis[i-1]))
            if (vis[i] || (i != 0 && nums[i] == nums[i - 1] && !vis[i - 1]))continue;
            else
            {
                path.push_back(nums[i]);
                vis[i] = 1;
                dfs(nums, pos + 1);
                path.pop_back();
                vis[i] = 0;
            }
        }
    }
};



////5.电话号码的字⺟组合
class Solution {
    vector<string> vv;
    string path;
    string hash[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
public:
    vector<string> letterCombinations(string digits)
    {
        if (digits == "")return vv;
        dfs(digits, 0);
        return vv;
    }
    void dfs(string nums, int pos)
    {
        if (path.size() == nums.size())
        {
            vv.push_back(path);
            return;
        }
        for (int i = pos; i < nums.size(); i++)
        {
            string s = hash[nums[i] - '0'];
            for (int j = 0; j < s.size(); j++)
            {
                path += s[j];
                dfs(nums, i + 1);
                path.pop_back();
            }
        }
    }
};




////6.括号⽣成
class Solution {
    vector<string> vv;
    string path;
    int _n;
    int left = 0, right = 0;
public:
    vector<string> generateParenthesis(int n)
    {
        _n = n;
        dfs();
        return vv;
    }
    void dfs()
    {
        if (path.size() == 2 * _n)
        {
            vv.push_back(path);
            return;
        }
        if (left < _n)
        {
            path += '(';
            left++;
            dfs();
            left--;
            path.pop_back();
        }
        if (right < left)
        {
            path += ')';
            right++;
            dfs();
            path.pop_back();
            right--;
        }
    }
};


////7.组合
class Solution {
    vector<vector<int>> vv;
    vector<int> path;
    int _k;
public:
    vector<vector<int>> combine(int n, int k)
    {
        _k = k;
        dfs(n, 1);
        return vv;
    }
    void dfs(int n, int pos)
    {
        if (path.size() == _k)
        {
            vv.push_back(path);
            return;
        }
        for (int i = pos; i <= n; i++)
        {
            path.push_back(i);
            dfs(n, i + 1);
            path.pop_back();
        }
    }
};



////8.目标和
class Solution {
    int cnt = 0;
    int sum = 0;
public:
    int findTargetSumWays(vector<int>& nums, int target)
    {
        dfs(nums, target, 0);
        return cnt;
    }
    void dfs(vector<int>& nums, int t, int pos)
    {
        if (pos == nums.size())
        {
            if (sum == t)cnt++;
            return;
        }
        sum += nums[pos];
        dfs(nums, t, pos + 1);
        sum -= nums[pos];

        sum += (-nums[pos]);
        dfs(nums, t, pos + 1);
        sum -= (-nums[pos]);
    }
};



////9.组合总和
class Solution {
    vector<vector<int>> vv;
    vector<int> path;
    int target;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int _target)
    {
        target = _target;
        dfs(candidates, 0, 0);
        return vv;
    }
    void dfs(vector<int>& candidates, int sum, int pos)
    {
        if (sum >= target)
        {
            if (sum == target)vv.push_back(path);
            return;
        }
        for (int i = pos; i < candidates.size(); i++)
        {
            path.push_back(candidates[i]);
            dfs(candidates, sum + candidates[i], i);
            path.pop_back();
        }
    }
};



class Solution {
    vector<vector<int>> vv;
    vector<int> path;
    int target;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int _target)
    {
        target = _target;
        dfs(candidates, 0, 0);
        return vv;
    }
    void dfs(vector<int>& candidates, int sum, int pos)
    {
        if (sum >= target)
        {
            if (sum == target)vv.push_back(path);
            return;
        }
        if (pos == candidates.size())return;
        for (int k = 0; k * candidates[pos] <= target; k++)
        {
            if (k)path.push_back(candidates[pos]);
            dfs(candidates, sum + candidates[pos] * k, pos + 1);
        }
        for (int k = 1; k * candidates[pos] <= target; k++)
        {
            path.pop_back();
        }
    }
};




////10.字⺟⼤⼩写全排列
class Solution {
    vector<string> vv;
    string path;
public:
    vector<string> letterCasePermutation(string s)
    {
        dfs(s, 0);
        return vv;
    }
    void dfs(string& s, int pos)
    {
        if (pos == s.size())
        {
            vv.push_back(path);
            return;
        }
        if (s[pos] >= 'a' && s[pos] <= 'z')
        {
            path += s[pos];
            dfs(s, pos + 1);
            path.pop_back();

            path += (s[pos] - 32);
            dfs(s, pos + 1);
            path.pop_back();
        }
        else if (s[pos] >= 'A' && s[pos] <= 'Z')
        {
            path += s[pos];
            dfs(s, pos + 1);
            path.pop_back();

            path += (s[pos] + 32);
            dfs(s, pos + 1);
            path.pop_back();
        }
        else
        {
            path += s[pos];
            dfs(s, pos + 1);
            path.pop_back();
        }
    }
};




////11.优美的排列
class Solution {
    int cnt = 0;
    int vis[20] = { 0 };
public:
    int countArrangement(int n)
    {
        dfs(n, 1);
        return cnt;
    }
    void dfs(int n, int pos)
    {
        if (pos == n + 1)
        {
            cnt++;
            return;
        }
        for (int i = 1; i <= n; i++)
        {
            if ((i % pos == 0 || pos % i == 0) && !vis[i])
            {
                vis[i] = 1;
                dfs(n, pos + 1);
                vis[i] = 0;
            }
        }
    }
};




////12.N 皇后
class Solution {
    vector<vector<string>> vv;
    vector<string> path;
    int checkcol[10], checkdig1[20], checkdig2[20];
public:
    vector<vector<string>> solveNQueens(int n)
    {
        path.resize(n);
        for (int i = 0; i < n; i++)
            path[i].append(n, '.');
        dfs(n, 0);
        return vv;
    }

    void dfs(int n, int row)
    {
        if (row == n)
        {
            vv.push_back(path);
            return;
        }
        for (int col = 0; col < n; col++)
        {
            if (!checkcol[col] && !checkdig1[row - col + n] && !checkdig2[col + row])
            {
                path[row][col] = 'Q';
                checkcol[col] = checkdig1[row - col + n] = checkdig2[col + row] = 1;
                dfs(n, row + 1);
                path[row][col] = '.';
                checkcol[col] = checkdig1[row - col + n] = checkdig2[col + row] = 0;
            }
        }
    }
};



////13.有效的数独
class Solution {
    int row[9][10] = { 0 }, col[9][10] = { 0 };
    int grid[3][3][10] = { 0 };
public:
    bool isValidSudoku(vector<vector<char>>& board)
    {
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                if (board[i][j] != '.')
                {
                    int tmp = board[i][j] - '0';
                    if (!row[i][tmp] && !col[j][tmp] && !grid[i / 3][j / 3][tmp])
                    {
                        row[i][tmp] = col[j][tmp] = grid[i / 3][j / 3][tmp] = 1;
                    }
                    else return false;
                }
            }
        }
        return true;
    }
};





////14.解数独
class Solution {
    int checkrow[9][10] = { 0 }, checkcol[9][10] = { 0 };
    int checkgrid[3][3][10] = { 0 };
public:
    void solveSudoku(vector<vector<char>>& board)
    {
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                if (board[i][j] != '.')
                {
                    int tmp = board[i][j] - '0';
                    checkrow[i][tmp] = checkcol[j][tmp] = checkgrid[i / 3][j / 3][tmp] = 1;
                }
            }
        }
        dfs(board);
    }
    bool dfs(vector<vector<char>>& board)
    {
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                if (board[i][j] == '.')
                {
                    for (int k = 1; k <= 9; k++)
                    {
                        if (!checkrow[i][k] && !checkcol[j][k] && !checkgrid[i / 3][j / 3][k])
                        {
                            board[i][j] = k + '0';
                            checkrow[i][k] = checkcol[j][k] = checkgrid[i / 3][j / 3][k] = 1;
                            if (dfs(board))return true;//先调用dfs,dfs返回才进行if判断
                            board[i][j] = '.';
                            checkrow[i][k] = checkcol[j][k] = checkgrid[i / 3][j / 3][k] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
};





////15.单词搜索
class Solution {
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int vis[7][7] = { 0 };
    int pos = 0;
public:
    bool exist(vector<vector<char>>& board, string word)
    {
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                char tmp = word[pos];
                if (board[i][j] == tmp && !vis[i][j])
                {
                    vis[i][j] = 1;
                    if (dfs(board, i, j, word, pos + 1))return true;
                    vis[i][j] = 0;
                }
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board, int a, int b, string word, int pos)
    {
        if (pos == word.size())return true;
        for (int k = 0; k < 4; k++)
        {
            int x = a + dx[k], y = b + dy[k];
            if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && !vis[x][y] && board[x][y] == word[pos])
            {
                vis[x][y] = 1;
                if (dfs(board, x, y, word, pos + 1))return true;
                vis[x][y] = 0;
            }
        }
        return false;
    }
};




////16.⻩⾦矿⼯
class Solution {
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int vis[110][110] = { 0 };
    int ret = 0, ans = 0;
    int n, m;
public:
    int getMaximumGold(vector<vector<int>>& grid)
    {
        n = grid.size(); m = grid[0].size();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (grid[i][j] != 0)
                {
                    ret += grid[i][j];
                    vis[i][j] = 1;
                    dfs(grid, i, j);
                    ret -= grid[i][j];
                    vis[i][j] = 0;
                }
            }
        }
        return ans;
    }
    void dfs(vector<vector<int>>& grid, int a, int b)
    {
        ans = max(ans, ret);
        for (int k = 0; k < 4; k++)
        {
            int x = a + dx[k], y = b + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] != 0 && !vis[x][y])
            {
                ret += grid[x][y];
                vis[x][y] = 1;
                dfs(grid, x, y);
                ret -= grid[x][y];
                vis[x][y] = 0;
            }
            //这里不能这样写
            //假设您从网格的一个边缘开始，并在第一次尝试向右移动时越界。
            //如果您在这个点更新 ans，那么您就没有机会探索从当前点向下或向左移动的可能性，这些路径可能包含更多的金币。
            // else if(x<0||x>=n||y<0||y>=m)
            // {
            //     ans=max(ans,ret)；
            //     return;
            // }
        }
    }
};




////17.不同路径 III
class Solution {
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { 1,-1,0,0 };
    int vis[25][25] = { 0 };
    int n, m;
    int cnt = 2, ret = 0;
    int bx, by;
public:
    int uniquePathsIII(vector<vector<int>>& grid)
    {
        n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (grid[i][j] == 0)cnt++;
                if (grid[i][j] == 1)
                {
                    bx = i;
                    by = j;
                }
            }
        }
        vis[bx][by] = 1;
        dfs(grid, bx, by, 1);
        return ret;
    }
    void dfs(vector<vector<int>>& grid, int a, int b, int pos)
    {
        if (grid[a][b] == 2)
        {
            if (pos == cnt)
                ret++;
            return;
        }
        for (int k = 0; k < 4; k++)
        {
            int x = a + dx[k], y = b + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] != -1 && !vis[x][y])
            {
                vis[x][y] = 1;
                dfs(grid, x, y, pos + 1);
                vis[x][y] = 0;
            }
        }
    }
};







////////二、floodfill算法
////1.图像渲染
class Solution {
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int n, m;
    int ret = 0;
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
    {
        n = image.size(); m = image[0].size();
        ret = image[sr][sc];
        if (ret == color)return image;
        else
            image[sr][sc] = color;
        dfs(image, sr, sc, color);
        return image;
    }
    void dfs(vector<vector<int>>& image, int a, int b, int color)
    {
        for (int k = 0; k < 4; k++)
        {
            int x = a + dx[k], y = b + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m && image[x][y] == ret)
            {
                image[x][y] = color;
                dfs(image, x, y, color);
            }
        }
    }
};




////2.岛屿数量
class Solution {
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int ret = 0, n, m;
    int vis[310][310] = { 0 };
public:
    int numIslands(vector<vector<char>>& grid)
    {
        n = grid.size(); m = grid[0].size();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (grid[i][j] == '1' && !vis[i][j])
                {
                    vis[i][j] = 1;
                    dfs(grid, i, j);
                    ret++;
                }
            }
        }
        return ret;
    }
    void dfs(vector<vector<char>>& grid, int a, int b)
    {
        for (int k = 0; k < 4; k++)
        {
            int x = a + dx[k], y = b + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == '1' && !vis[x][y])
            {
                vis[x][y] = 1;
                dfs(grid, x, y);
            }
        }
    }
};




////3.岛屿的最⼤⾯积
class Solution {
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int ret = 0, cnt = 0;
    int n, m;
    int vis[55][55] = { 0 };
public:
    int maxAreaOfIsland(vector<vector<int>>& grid)
    {
        n = grid.size(); m = grid[0].size();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (grid[i][j] == 1 && !vis[i][j])
                {
                    vis[i][j] = 1;
                    cnt = 1;
                    dfs(grid, i, j);
                    ret = max(ret, cnt);
                }
            }
        }
        return ret;
    }
    int dfs(vector<vector<int>>& grid, int a, int b)
    {
        for (int k = 0; k < 4; k++)
        {
            int x = a + dx[k], y = b + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1 && !vis[x][y])
            {
                vis[x][y] = 1;
                cnt++;
                dfs(grid, x, y);
            }
        }
        return cnt;
    }
};




////4.被围绕的区域
class Solution {
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int vis[210][210] = { 0 };
    int n, m;
public:
    void solve(vector<vector<char>>& board)
    {
        n = board.size(); m = board[0].size();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if ((i == 0 || i == n - 1 || j == 0 || j == m - 1) && board[i][j] == 'O')
                {
                    vis[i][j] = 1;
                    dfs(board, i, j);
                }
            }
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (!vis[i][j] && board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }
    void dfs(vector<vector<char>>& board, int a, int b)
    {
        for (int k = 0; k < 4; k++)
        {
            int x = a + dx[k], y = b + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m && board[x][y] == 'O' && !vis[x][y])
            {
                vis[x][y] = 1;
                dfs(board, x, y);
            }
        }
    }
};







////////四、记忆化搜索
////1.斐波那契数
class Solution {
public:
    int fib(int n)
    {
        return dfs(n);
    }
    int dfs(int n)
    {
        if (n == 0 || n == 1)
        {
            return n;
        }
        return dfs(n - 1) + dfs(n - 2);
    }
};
//---------------------------------------------------------------------------------------------- -
class Solution {
    int memo[35];
public:
    int fib(int n)
    {
        //初始化
        memset(memo, -1, sizeof(memo));
        return dfs(n);
    }
    int dfs(int n)
    {
        //往备忘录查找一下
        if (memo[n] != -1)return memo[n];
        if (n == 0 || n == 1)
        {
            memo[n] = n;//返回之前放到备忘录
            return n;
        }
        memo[n] = dfs(n - 1) + dfs(n - 2);//返回之前放到备忘录
        return memo[n];
    }
};
//------------------------------------------------------------------------------------------------ -
class Solution {
public:
    int fib(int n)
    {
        vector<int> dp(n + 2, 0);
        dp[0] = 0; dp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};




////2.不同路径
class Solution {
    int memo[110][110];
public:
    int uniquePaths(int m, int n)
    {
        return dfs(m, n);
    }
    int dfs(int i, int j)
    {
        if (memo[i][j] != 0)return memo[i][j];
        if (i == 0 || j == 0)
        {
            memo[i][j] = 0;
            return memo[i][j];
        }
        if (i == 1 && j == 1)
        {
            memo[i][j] = 1;
            return memo[i][j];
        }
        memo[i][j] = dfs(i - 1, j) + dfs(i, j - 1);
        return memo[i][j];
    }
};
//---------------------------------------------------------------------------------------------- -
class Solution {
public:
    int uniquePaths(int m, int n)
    {
        vector<vector<int>>dp(m + 1, vector<int>(n + 1, 0));
        dp[1][1] = 1;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (i == 1 && j == 1)continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
};




////3.最⻓递增⼦序列
class Solution {
public:
    int lengthOfLIS(vector<int>& nums)
    {
        int ret = 0;
        vector<int> memo(nums.size());
        for (int i = 0; i < nums.size(); i++)
        {
            ret = max(ret, dfs(i, nums, memo));
        }
        return ret;
    }
    int dfs(int pos, vector<int>& nums, vector<int>& memo)
    {
        if (memo[pos] != 0)return memo[pos];
        int ret = 1;
        for (int i = pos + 1; i < nums.size(); i++)
        {
            if (nums[i] > nums[pos])
            {
                ret = max(ret, dfs(i, nums, memo) + 1);
            }
        }
        memo[pos] = ret;
        return ret;
    }
};
//------------------------------------------------------------------------------------------------ -
class Solution {
    int ret = 0;
public:
    int lengthOfLIS(vector<int>& nums)
    {
        vector<int> dp(nums.size(), 1);
        for (int i = nums.size() - 1; i >= 0; i--)
        {
            for (int j = i + 1; j < nums.size(); j++)
            {
                if (nums[i] < nums[j])
                    dp[i] = max(dp[j] + 1, dp[i]);
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};





////4. 猜数字⼤⼩ II
class Solution {
    int memo[201][201] = { 0 };
public:
    int getMoneyAmount(int n)
    {
        return dfs(1, n);
    }
    int dfs(int left, int right)
    {
        if (left >= right)return 0;
        if (memo[left][right] != 0)return memo[left][right];
        int ret = INT_MAX;
        for (int head = left; head <= right; head++)
        {
            int x = dfs(left, head - 1);
            int y = dfs(head + 1, right);
            ret = min(ret, head + max(x, y));
        }
        memo[left][right] = ret;
        return ret;
    }
};




////5.矩阵中的最⻓递增路径
class Solution {
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int n, m;
public:
    int longestIncreasingPath(vector<vector<int>>& matrix)
    {
        n = matrix.size(); m = matrix[0].size();
        vector<vector<int>> memo(n, vector<int>(m, 0));
        int ret = 1;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                ret = max(ret, dfs(matrix, i, j, memo));
        return ret;
    }
    int dfs(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& memo)
    {
        if (memo[i][j] != 0)return memo[i][j];
        int ret = 1;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < n && y >= 0 && y<m && matrix[x][y]>matrix[i][j])
            {
                ret = max(ret, dfs(matrix, x, y, memo) + 1);
            }
        }
        memo[i][j] = ret;
        return ret;
    }
};
